package leetcode_回溯;

/**
 * 排列序列
 * 需要剪枝，因为只需要一个结果就可以了
 * 难就难在剪枝
 * 最后剪到只有最后两位时，结果为 1 ，则按顺序取，为 2，则反过来取
 *   比如最后只剩 1 4，结果为 1 ，则 14；为 2，则 41
 */
public class _60 {
    public static void main(String[] args) {
        System.out.println(new _60().getPermutation(3, 5));
    }

    public String getPermutation(int n, int k) {
        StringBuilder ans = new StringBuilder();
        boolean[] used = new boolean[n + 1];
        dfs(n, k, ans, used);
        return ans.toString();
    }

    public int factorial(int n) {
        return n == 1 ? 1 : n * (factorial(n - 1));
    }

    public void swap(StringBuilder ans) {
        char t1 = ans.charAt(ans.length() - 1), t2 = ans.charAt(ans.length() - 2);
        ans.delete(ans.length() - 2, ans.length());
        ans.append(t1);
        ans.append(t2);
    }

    public void dfs(int n, int k, StringBuilder ans, boolean[] used) {
        if (k == 1 || k == 2) {
            for (int i = 1; i <= n; i++) {
                if (!used[i]) {
                    ans.append(i);
                }
            }
            if (k == 2) {
                swap(ans);
            }
            return;
        }
        int count = 0;
        int f = factorial( n - ans.length() - 1);
        for (int i = 1; i <= n; i++) {
            if (!used[i]) {
                ++count;
                if (k > count * f) {
                    continue;
                }
                ans.append(i);
                used[i] = true;
                dfs(n, k - (count - 1) * f, ans, used);
                break;
            }
        }
    }
}
